package 中等.模拟;

/**
 * 一个句子是由一些单词与它们之间的单个空格组成，且句子的开头和结尾没有多余空格。
 * 比方说，"Hello World" ，"HELLO" ，"hello world hello world" 都是句子。每
 * 个单词都 只 包含大写和小写英文字母。
 * 如果两个句子 sentence1 和 sentence2 ，可以通过往其中一个句子插入一个任意的
 * 句子（可以是空句子）而得到另一个句子，那么我们称这两个句子是 相似的 。比方说，
 * sentence1 = "Hello my name is Jane" 且 sentence2 = "Hello Jane" ，我们可以
 * 往 sentence2 中 "Hello" 和 "Jane" 之间插入 "my name is" 得到 sentence1 。
 * 给你两个句子 sentence1 和 sentence2 ，如果 sentence1 和 sentence2 是相似的，
 * 请你返回 true ，否则返回 false 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/sentence-similarity-iii
 */
public class 句子相似性III_1813 {

    public static void main(String[] args) {

        句子相似性III_1813 impl = new 句子相似性III_1813();
        System.out.println(impl.areSentencesSimilar("A B C D B B",
                "A B B"));

    }

    /**
     * 模拟+双指针
     * 1， 选择一个单词较少的句子插入 一个句子 得到和另外一个句子
     * 2，如果两个句子右边的单词有连续相等的，那么优先将右边
     * 的单词抵消
     */
    public boolean areSentencesSimilar(String sentence1, String sentence2) {
        if (sentence1.length() < sentence2.length()) {
            return similar(sentence1, sentence2);
        } else {
            return similar(sentence2, sentence1);
        }
    }

    private boolean similar(String sentence1, String sentence2) {
        String[] arr1 = sentence1.split(" ");
        String[] arr2 = sentence2.split(" ");

        int left1 = 0, left2 = 0;
        int right1 = arr1.length - 1, right2 = arr2.length - 1;

        while (right1 >= 0 && right2 >= 0 && arr1[right1].equals(arr2[right2])) {
            right1--;
            right2--;
        }

        boolean hasAddStr = false;
        while (left1 <= right1 && left2 <= right2) {
            if (!arr1[left1].equals(arr2[left2])) {
                if (hasAddStr) {
                    return false;
                }
                hasAddStr = true;
            }

            while (left2 <= right2 && !arr1[left1].equals(arr2[left2])) {
                left2++;
            }
            left1++;
            left2++;
        }
        return left1 == right1 + 1 && (left2 == right2 + 1 || !hasAddStr);
    }

}
